package 递归回溯;

public class No357计算各个位数不同的数字个数 {

    /**
     * 给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10^n 。
     *
     * 示例:
     * 输入: 2
     * 输出: 91
     * 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。
     */

    private int count;
    private boolean[] flag=new boolean[10];

    public int countNumbersWithUniqueDigits(int n) {
        dg(n,0);
        return count;
    }

    /**
     * 回溯思路:将n长度的数字拆成一个个的字符
     */
    private void dg(int n,int size){

        if(n==size)
            return;

        for (int i = 0; i < 10; i++) {
            //以0开始,并且长度大于1时
            if (i == 0 && size == 1)
                continue;
            if(flag[i])
                continue;
            count++;
            flag[i]=true;
            dg(n,size+1);
            flag[i]=false;
        }

    }

    public static void main(String[] args) {
        No357计算各个位数不同的数字个数 n=new No357计算各个位数不同的数字个数();
        int i = n.countNumbersWithUniqueDigits(2);
        System.out.println(i);
    }

}
